package main

func mergeSort(nums []int) {
	if len(nums) < 2 {
		return
	}
	mid := len(nums) / 2
	mergeSort(nums[:mid])
	mergeSort(nums[mid:])
	merge(nums, mid)
}

func reverse(arr []int) {
	i := 0
	j := len(arr) - 1
	for i < j {
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
}

/*
 * 举例: nums = []int{1, 3, 5, 2, 4, 6}, mid = 3
 * 我们令: i := 0, j := mid, i往后移动到第一个使arr[i]>arr[j]的位置(此时的 j 即是 mid), j往后移动到第一个使arr[j]>=arr[i]的位置,
 * 此时数组被分为四部分(四个部分均为左闭右开区间):
 *              i                mid            j
 * |------------|-----------------|-------------|------------|
 *   x<arr[mid]    x >= arr[mid]     x < arr[i]      其它
 *	               && x >= arr[i]
 *       [1]          [3, 5]            [2]        [4, 6]
 *
 * 只要将第二部分和第三部分调换即可完成 arr[i:j] 部分的排序.(记住, 1,3,5,2,4,6这个例子就好了, 不用死记硬背)
 *
 * 剩下的问题是如何调换第二部分和第三部分
 * 假设我们有两个序列: 0, 1, ... k 和 k+1,k+2, ..., n
 * 先将两个序列各自倒序: k, ..., 1, 0 和 n, ..., k+2, k+1
 * 将两个序列整体合并然后倒序: k+1, k+2, ..., n, 0, 1, 2, ..., k
 */
func merge(nums []int, mid int) {
	i := 0
	j := mid
	for i < j && j < len(nums) {
		for i < j && nums[i] <= nums[j] {
			i++
		}
		step := 0
		for j < len(nums) && nums[j] < nums[i] {
			j++
			step++
		}
		reverse(nums[i : j-step])
		reverse(nums[j-step : j])
		reverse(nums[i:j])
		i += step
	}
}

func main() {
	nums := []int{1, 3, 5, 2, 4, 6, 8}
	merge(nums, 3)
	//mergeSort(nums)
	println(nums)
}
